//Accepted
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
 
using namespace std;
typedef long long ll;

long long  i, j;
int n, k, t;
char c[21];

void process(){
	scanf("%d%s", &n, c);
	k=strlen(c);
	for(j=n,i=1;j>1;j-=k){
		i*=j;
	}
	cout<< i<<endl;
}
int main(){
	//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
	scanf("%d", &t);
	while(t--){
		process();
	}
	return 0;
}
